The present invention relates to cryptographic algorithms and, in particular, to algorithms for determining an inverse of a value related to a modulus.
Computations of inverses, in particular, a computation of the modular multiplicative inverse Z0−1 mod N0, wherein Z0 and N0 are two non-negative integers with gcd(Z0,N0)=1 (gcd=greatest common divisor) are e.g. an important component when determining cryptographic keys. They are needed e.g. when determining cryptographic keys for the RSA-algorithm (named after Ron Rivest, Adi Shamir and Leonard Adleman) or other cryptographic algorithms as e.g. the ECDSA-algorithm (ECDSA=Elliptic Curve Digital Signature Algorithm). In this context, the integer Z0 or N0 is a secret that should not be revealed by an attacker.
The common algorithm used for computing Z0−1 mod N0 is the extended Euclidean algorithm which results from the Euclidean algorithm that is extended so that it not only yields the greatest common divisor of two integers Z0 and N0, but also integers x and y satisfying Z0x+N0y=d, where d=gcd(Z0,N0).
The extended Euclidean algorithm contains a division in an iteration loop (e.g. a while-loop) wherein the division is again typically realized by another iteration loop in which the involved integers are shifted and subtracted or added.
There are several methods to restructure the extended Euclidean algorithm to realize it on a microprocessor. Typically, all these methods or variants have one thing in common: They consist of an outer and an inner iteration loop, wherein the outer iteration loop corresponds to a loop exchanging integer pairs and the inner loop corresponds to the implementation of the division. Routines of this kind are susceptible to SPA (SPA=Simple Power Analysis) attacks since the current or power consumption and, additionally, the time consumption depend on the numbers to be processed. An attacker could thus draw conclusions as to the numbers processed from the current or time profile and thus for example spy out a secret key of a public-key crypto algorithm as e.g. the input Z0.
Hence, it is desirable to implement the division within the outer iteration loop more securely.